package com.zklh.leetcode.top100.problem207;

import java.util.*;

/**
 * 课程表深度优先搜索算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/31
 */
public class Solution2 {
    List<List<Integer>> edges;
    int[] visited;
    boolean valid = true;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<>());
        }

        for (int[] prerequisite : prerequisites) {
            edges.get(prerequisite[1]).add(prerequisite[0]);
        }

        visited = new int[numCourses+1];

        for (int i = 0; i < numCourses; i++) {
            dfs(i);
        }
        return valid;
    }

    private void dfs(int course) {
        if (visited[course] == 0) {
            visited[course] = 1;
            for (Integer i : edges.get(course)) {
                dfs(i);
            }
        } else if (visited[course] == 1) {
            valid = false;
            return;
        }
        visited[course] = 2;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
/*        int numCourses = 2;
        int[][] prerequisites = {{1,0}};*/

/*        int numCourses = 4;
        int[][] prerequisites = {{0,1},{3,1},{1,3},{3,2}};*/

        int numCourses = 8;
        int[][] prerequisites = {{1,0},{2,6},{1,7},{6,4},{7,0},{0,5}};
        System.out.println(solution2.canFinish(numCourses, prerequisites));
    }

}